package 剑指offer;


import FloodFill.Interval;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @description:
 * @author: ywk
 * @date: 2021-04-02
 */
public class 树的直径 {
    static int maxVal = 0;

    class Node {
        int id, dist;

        public Node() {
        }

        public Node(int id, int dist) {
            this.id = id;
            this.dist = dist;
        }
    }

    LinkedList<Node>[] nodes;


    public int solve(int n, Interval[] Tree_edge, int[] Edge_value) {
        // write code here
        nodes = new LinkedList[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new LinkedList();
        }
        //添加该节点的所有邻接节点
        for (int i = 0; i < n - 1; i++) {
            int x = Tree_edge[i].start, y = Tree_edge[i].end;
            nodes[x].add(new Node(y, Edge_value[i]));
            nodes[y].add(new Node(x, Edge_value[i]));
        }
        dfs(0, -1);
        return maxVal;
    }

    private int dfs(int root, int parent) {
        List<Integer> list = new ArrayList<>();
        for (Node v : nodes[root]) {
            if (v.id == parent) {
                continue;
            }
            list.add(dfs(v.id, root) + v.dist);
        }
        Collections.sort(list);
        int n = list.size(), val = 0;
        for (int i = n - 1; i >= 0 && i >= n - 2; --i) {
            val += list.get(i);
        }
        maxVal = Math.max(maxVal, val);
        return n == 0 ? 0 : list.get(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(new 树的直径().solve(6, new Interval[]{new Interval(0, 1), new Interval(1, 5),
                        new Interval(1, 2), new Interval(2, 3),
                        new Interval(2, 4)},
                new int[]{1, 2, 3, 4, 5}));

    }
}
